"""
代码说明：
新增了level_order_traversal函数，用于动态层序遍历二叉树
采用分层处理的思路，使用队列存储当前层的所有节点
遍历当前层节点时，收集节点值并将子节点加入下一层队列
直到当前层为空时结束遍历，实现了真正的动态层次遍历
增加了多个测试用例，验证不同结构二叉树的遍历结果
这种实现方式不需要预先知道树的结构，完全根据输入的二叉树动态生成层序遍历结果，适用于任何合法的二叉树结构。
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def create_binary_tree(arr):
    """根据列表创建二叉树（层序遍历方式）"""
    if not arr:
        return None
    # 创建根节点
    root = TreeNode(arr[0])
    # 使用队列存储待处理节点
    queue = [root]
    index = 1  # 当前处理的列表索引
    while queue and index < len(arr):
        # 取出队首节点
        current = queue.pop(0)
        # 处理左子节点
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        # 处理右子节点
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root


#正式层序遍历 无需预先知道二叉树的结构
def level_order_traversal(root):
    """动态层序遍历二叉树，返回每层节点值的列表"""
    if not root:
        return []
    result = []
    # 使用队列存储当前层的节点
    current_level = [root]
    #当前层的节点有值 才有的玩
    while current_level:
        # 存储当前层的节点值
        level_values = []
        # 存储下一层的节点
        next_level = []
        # 遍历当前层的所有节点
        for node in current_level:
            level_values.append(node.val)
            # 将左子节点加入下一层
            if node.left:
                next_level.append(node.left)
            # 将右子节点加入下一层
            if node.right:
                next_level.append(node.right)
        # 将当前层的值加入结果
        result.append(level_values)
        # 继续迭代处理下一层
        current_level = next_level
    return result


# 测试
if __name__ == "__main__":
    # 测试用例1
    arr1 = [1, 2, 3, None, 4, 5, None]
    root1 = create_binary_tree(arr1)
    print("测试用例1的层序遍历结果：")
    print(level_order_traversal(root1))  # 输出: [[1], [2, 3], [4, 5]]

    # 测试用例2（空树）
    arr2 = []
    root2 = create_binary_tree(arr2)
    print("测试用例2的层序遍历结果：")
    print(level_order_traversal(root2))  # 输出: []

    # 测试用例3（单节点）
    arr3 = [10]
    root3 = create_binary_tree(arr3)
    print("测试用例3的层序遍历结果：")
    print(level_order_traversal(root3))  # 输出: [[10]]

    # 测试用例4
    arr4 = [3, 9, 20, None, None, 15, 7]
    root4 = create_binary_tree(arr4)
    print("测试用例4的层序遍历结果：")
    print(level_order_traversal(root4))  # 输出: [[3], [9, 20], [15, 7]]